From 13a4f5e4b7b49e2aee0b139ab7ad93bba64185d4 Mon Sep 17 00:00:00 2001 From: tsteven4 <13596209+tsteven4@users.noreply.github.com> Date: Thu, 20 Jul 2023 14:45:02 -0600 Subject: [PATCH] reduce complexity of gdb waypt searchs from O(n^2) to O(n) (#1141) * use QHash for gdb waypoint searches. This reduces the complexity from O(n^2) to O(n). For the reader two parallel hashes are maintained with different keys but identical values. This is necessary because sometimes we want to match the name and position, and other times we just want to match the name. * workaround missing qHashMulti in Qt5. and supply missing default for our qHash functions. * fix MSVC C2666 errors due to an erroneous assumption. In Qt6 the return type of qHash, and the type of the seed, happens to be the same as QHash::size_type. However, this isn't true in Qt5. --- defs.h | 6 ++++ gdb.cc | 94 +++++++++++++++++++++++++++++++++++++--------------------- gdb.h | 63 +++++++++++++++++++++++++++++++++++---- 3 files changed, 124 insertions(+), 39 deletions(-) diff --git a/defs.h b/defs.h index 5794729a7..f417e52b0 100644 --- a/defs.h +++ b/defs.h @@ -1127,4 +1127,10 @@ int color_to_bbggrr(const char* cname); constexpr double unknown_alt = -99999999.0; constexpr int unknown_color = -1; +#if (QT_VERSION < QT_VERSION_CHECK(6, 0, 0)) +using qhash_result_t = uint; +#else +using qhash_result_t = size_t; +#endif + #endif // DEFS_H_INCLUDED_ diff --git a/gdb.cc b/gdb.cc index 50378df05..347af342f 100644 --- a/gdb.cc +++ b/gdb.cc @@ -29,7 +29,6 @@ #include // for QByteArray, operator== #include // for QDate #include // for QDateTime -#include // for QList<>::const_iterator, QList #include // for QString, operator!=, operator== #include // for QTime #include // for CaseInsensitive @@ -70,12 +69,26 @@ #define DBG(a, b) if ((GDB_DEBUG & (a)) && (b)) + +inline bool operator==(const GdbFormat::WptNameKey& lhs, const GdbFormat::WptNameKey &rhs) noexcept +{ + return lhs.shortname.compare(rhs.shortname, Qt::CaseInsensitive) == 0; +} + +inline bool operator==(const GdbFormat::WptNamePosnKey& lhs, const GdbFormat::WptNamePosnKey &rhs) noexcept +{ + return + (lhs.shortname.compare(rhs.shortname, Qt::CaseInsensitive) == 0) && + lhs.lat == rhs.lat && + lhs.lon == rhs.lon; +} + void -GdbFormat::gdb_flush_waypt_queue(QList* Q) +GdbFormat::gdb_flush_waypt_queue(WptNamePosnHash& Q) { - while (!Q->isEmpty()) { - const Waypoint* wpt = Q->takeFirst(); + for (auto it = Q.cbegin(), end = Q.cend(); it != end; ++it) { + const Waypoint* wpt = it.value(); if (wpt->extra_data) { // wpt->extra_data may be holding a pointer to a QString, courtesy // the grossness at the end of write_waypoint_cb(). @@ -83,6 +96,7 @@ GdbFormat::gdb_flush_waypt_queue(QList* Q) } delete wpt; } + Q = WptNamePosnHash(); } #if GDB_DEBUG @@ -194,31 +208,37 @@ GdbFormat::gdb_fread_strlist() const return qres; } -Waypoint* -GdbFormat::gdb_find_wayptq(const QList* Q, const Waypoint* wpt, const char exact) +Waypoint* GdbFormat::gdb_find_wayptq(const WptNameHash& Q, const Waypoint* wpt) { - QString name = wpt->shortname; - foreach (Waypoint* tmp, *Q) { - if (name.compare(tmp->shortname,Qt::CaseInsensitive) == 0) { - if (! exact) { - return tmp; - } + if (Q.contains(wpt->shortname)) { + return Q.value(wpt->shortname); + } + return nullptr; +} - if ((tmp->latitude == wpt->latitude) && - (tmp->longitude == wpt->longitude)) { - return tmp; - } - } +Waypoint* GdbFormat::gdb_find_wayptq(const WptNamePosnHash& Q, const Waypoint* wpt) +{ + auto key = WptNamePosnKey(wpt->shortname, wpt->latitude, wpt->longitude); + if (Q.contains(key)) { + return Q.value(key); } return nullptr; } Waypoint* -GdbFormat::gdb_reader_find_waypt(const Waypoint* wpt, const char exact) const +GdbFormat::gdb_reader_find_waypt(const Waypoint* wpt, bool exact) const { - Waypoint* res = gdb_find_wayptq(&wayptq_in, wpt, exact); - if (res == nullptr) { - res = gdb_find_wayptq(&wayptq_in_hidden, wpt, exact); + Waypoint* res; + if (exact) { + res = gdb_find_wayptq(waypt_nameposn_in_hash, wpt); + if (res == nullptr) { + res = gdb_find_wayptq(waypt_nameposn_in_hidden_hash, wpt); + } + } else { + res = gdb_find_wayptq(waypt_name_in_hash, wpt); + if (res == nullptr) { + res = gdb_find_wayptq(waypt_name_in_hidden_hash, wpt); + } } return res; } @@ -226,7 +246,7 @@ GdbFormat::gdb_reader_find_waypt(const Waypoint* wpt, const char exact) const Waypoint* GdbFormat::gdb_add_route_waypt(route_head* rte, Waypoint* ref, const int wpt_class) const { - Waypoint* tmp = gdb_reader_find_waypt(ref, 1); + Waypoint* tmp = gdb_reader_find_waypt(ref, true); if (tmp == nullptr) { tmp = find_waypt_by_name(ref->shortname); if (tmp == nullptr) { @@ -779,7 +799,7 @@ GdbFormat::read_route() if (links == 0) { /* Without links we need all information from wpt */ - Waypoint* tmp = gdb_reader_find_waypt(wpt, 0); + Waypoint* tmp = gdb_reader_find_waypt(wpt, false); if (tmp != nullptr) { delete wpt; wpt = new Waypoint(*tmp); @@ -946,8 +966,10 @@ GdbFormat::rd_init(const QString& fname) ftmp = gbfopen_le(nullptr, "wb", MYNAME); read_file_header(); - wayptq_in.clear(); - wayptq_in_hidden.clear(); + waypt_nameposn_in_hash.clear(); + waypt_name_in_hash.clear(); + waypt_nameposn_in_hidden_hash.clear(); + waypt_name_in_hidden_hash.clear(); bool via = gdb_opt_via; bool drop_wpt = gdb_opt_drop_hidden_wpt; @@ -967,8 +989,10 @@ void GdbFormat::rd_deinit() { disp_summary(fin); - gdb_flush_waypt_queue(&wayptq_in); - gdb_flush_waypt_queue(&wayptq_in_hidden); + gdb_flush_waypt_queue(waypt_nameposn_in_hash); + waypt_name_in_hash = WptNameHash(); /* values already flushed */ + gdb_flush_waypt_queue(waypt_nameposn_in_hidden_hash); + waypt_name_in_hidden_hash = WptNameHash(); /* values already flushed */ gbfclose(ftmp); gbfclose(fin); } @@ -1009,9 +1033,11 @@ GdbFormat::read() if (!gdb_hide_wpt || (wpt_class == 0)) { waypt_add(wpt); auto* dupe = new Waypoint(*wpt); - wayptq_in.append(dupe); + waypt_nameposn_in_hash.insert(WptNamePosnKey(wpt->shortname, wpt->latitude, wpt->longitude), dupe); + waypt_name_in_hash.insert(wpt->shortname, dupe); } else { - wayptq_in_hidden.append(wpt); + waypt_nameposn_in_hidden_hash.insert(WptNamePosnKey(wpt->shortname, wpt->latitude, wpt->longitude), wpt); + waypt_name_in_hidden_hash.insert(wpt->shortname, wpt); } break; case 'R': @@ -1359,7 +1385,7 @@ GdbFormat::write_route(const route_head* rte, const QString& rte_name) gdb_check_waypt(next); } - Waypoint* test = gdb_find_wayptq(&wayptq_out, wpt, 1); + Waypoint* test = gdb_find_wayptq(waypt_nameposn_out_hash, wpt); if (test != nullptr) { wpt = test; } else { @@ -1512,7 +1538,7 @@ GdbFormat::write_waypoint_cb(const Waypoint* refpt) /* do this when backup always happens in main */ // but, but, casting away the const here is wrong... (const_cast(refpt))->shortname = refpt->shortname.trimmed(); - Waypoint* test = gdb_find_wayptq(&wayptq_out, refpt, 1); + Waypoint* test = gdb_find_wayptq(waypt_nameposn_out_hash, refpt); if (refpt->HasUrlLink() && test && test->HasUrlLink() && route_flag == 0) { UrlLink orig_link = refpt->GetUrlLink(); @@ -1533,7 +1559,7 @@ GdbFormat::write_waypoint_cb(const Waypoint* refpt) auto* wpt = new Waypoint(*refpt); gdb_check_waypt(wpt); - wayptq_out.append(wpt); + waypt_nameposn_out_hash.insert(WptNamePosnKey(wpt->shortname, wpt->latitude, wpt->longitude), wpt); gbfile* fsave = fout; fout = ftmp; @@ -1662,7 +1688,7 @@ GdbFormat::wr_init(const QString& fname) gdb_category = strtol(gdb_opt_bitcategory, nullptr, 0); } - wayptq_out.clear(); + waypt_nameposn_out_hash.clear(); short_h = nullptr; waypt_ct = 0; @@ -1677,7 +1703,7 @@ void GdbFormat::wr_deinit() { disp_summary(fout); - gdb_flush_waypt_queue(&wayptq_out); + gdb_flush_waypt_queue(waypt_nameposn_out_hash); mkshort_del_handle(&short_h); gbfclose(fout); gbfclose(ftmp); diff --git a/gdb.h b/gdb.h index 2ffa8887c..b418a51a1 100644 --- a/gdb.h +++ b/gdb.h @@ -26,10 +26,11 @@ #ifndef GDB_H_INCLUDED_ #define GDB_H_INCLUDED_ -#include // for QList +#include // for QHash<>::const_iterator, QHash<>::key_iterator, qHash, qHashMulti, QHash #include // for QString #include // for QStringView #include // for QVector +#include // for QT_VERSION, QT_VERSION_CHECK #include "defs.h" // for arglist_t, Waypoint, route_head, ARGTYPE_BOOL, ARGTYPE_INT, ARG_NOMINMAX, bounds, FF_CAP_RW_ALL, ff_cap, ff_type, ff_type_file, short_handle #include "format.h" // for Format @@ -63,6 +64,53 @@ public: void write() override; void wr_deinit() override; + /* Types */ + + // see https://www.kdab.com/how-to-declare-a-qhash-overload/ + class WptNamePosnKey; + using WptNamePosnHash = QHash; + class WptNamePosnKey { + public: + WptNamePosnKey(const QString& name, double lt, double ln) : shortname(name), lat(lt), lon(ln) {} + + friend qhash_result_t qHash(const WptNamePosnKey &c, qhash_result_t seed = 0) noexcept + { +#if (QT_VERSION >= QT_VERSION_CHECK(6, 0, 0)) + return qHashMulti(seed, c.shortname.toUpper(), c.lat, c.lon); +#else + /* + * As noted in above refeference + * QtPrivate::QHashCombine is private API, but does not require any special buildsystem magic; + * it’s in , a public header. + */ + QtPrivate::QHashCombine hash; + + seed = hash(seed, c.shortname.toUpper()); + seed = hash(seed, c.lat); + seed = hash(seed, c.lon); + return seed; +#endif + } + + QString shortname; + double lat{}; + double lon{}; + }; + + class WptNameKey; + using WptNameHash = QHash; + class WptNameKey { + public: + WptNameKey(const QString& name) : shortname(name) {} /* converting constructor */ + + friend qhash_result_t qHash(const WptNameKey &c, qhash_result_t seed = 0) noexcept + { + return qHash(c.shortname.toUpper(), seed); + } + + QString shortname; + }; + private: /* Constants */ @@ -80,13 +128,14 @@ private: /* Member Functions */ - static void gdb_flush_waypt_queue(QList* Q); + static void gdb_flush_waypt_queue(WptNamePosnHash& Q); void disp_summary(const gbfile* f) const; QString fread_cstr() const; static char* gdb_fread_cstr(gbfile* file_in); QString gdb_fread_strlist() const; - static Waypoint* gdb_find_wayptq(const QList* Q, const Waypoint* wpt, char exact); - Waypoint* gdb_reader_find_waypt(const Waypoint* wpt, char exact) const; + static Waypoint* gdb_find_wayptq(const WptNameHash& Q, const Waypoint* wpt); + static Waypoint* gdb_find_wayptq(const WptNamePosnHash& Q, const Waypoint* wpt); + Waypoint* gdb_reader_find_waypt(const Waypoint* wpt, bool exact) const; Waypoint* gdb_add_route_waypt(route_head* rte, Waypoint* ref, int wpt_class) const; static QString gdb_to_ISO8601_duration(unsigned int seconds); void gdb_write_cstr(QStringView a = QStringView()) const; @@ -118,7 +167,11 @@ private: bool gdb_hide_wpt{}; bool gdb_hide_rpt{}; - QList wayptq_in, wayptq_out, wayptq_in_hidden; + WptNamePosnHash waypt_nameposn_in_hash; + WptNameHash waypt_name_in_hash; + WptNamePosnHash waypt_nameposn_in_hidden_hash; + WptNameHash waypt_name_in_hidden_hash; + WptNamePosnHash waypt_nameposn_out_hash; short_handle short_h{}; char* gdb_opt_category{}; -- 2.30.2